#!/usr/bin/env python3

from typing import List
import time


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount in coins:
            return 1
        elif amount <= 0:
            return float('inf')
        else:
            lat = []
            for i in coins:
                lat.append(1+self.coinChange(coins, amount-i))
            return min(lat)

    def coinChange_note(self, coins: List[int], amount: int) -> int:
        if amount == 0: return 0
        note = {}
        for i in coins:
            note[i] = 1
        def helper(amount):
            if amount <= 0:
                return float('inf')
            else:
                try:
                    tmp = note[amount]
                except:
                    lat = []
                    for i in coins:
                        lat.append(1+helper(amount-i))
                    tmp = min(lat)
                    note[amount] = tmp
                return tmp
        result = helper(amount)
        if result == float('inf'):
            return -1
        else:
            return result

    def coinChange_dp(self, coins: List[int], amount: int) -> int:
        def helper(depth = 0, s = {0}):
            if amount in s:
                return depth
            if len(s) == 0:
                return -1
            tmp = set()
            for n in s:
                for c in coins:
                    v = n + c
                    if v <= amount:
                        tmp.add(n+c)
            return helper(depth+1, tmp)
        return helper()


if __name__ == "__main__":
    s = Solution()
    coins = [71,440,63,321,461,310,467,456,361]
    amount = 9298
    print(s.coinChange_note(coins, amount))
